{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# 牛顿插值法\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "from scipy.optimize import newton\n",
    "\n",
    "# 输入数据路径,需要使用Excel格式；\n",
    "inputfile = '../Data/missing_data.xls'\n",
    "# 输出数据路径,需要使用Excel格式\n",
    "outputfile = '../Data/Temp/newton_missing_data_processed.xls'\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(5, 0), (12, 0), (3, 1), (10, 1), (19, 1), (20, 1), (4, 2), (7, 2), (10, 2), (16, 2)]\n"
     ]
    }
   ],
   "source": [
    "# 读入数据\n",
    "data = pd.read_excel(inputfile, header=None, names=['A', 'B', 'C'])\n",
    "# 判断DataFrame中空值的位置（行，列）\n",
    "NULL_value_position = []\n",
    "for j in range(len(data.columns)):\n",
    "    value_column = data[data.columns[j]].isnull()\n",
    "    for i in range(len(value_column)):\n",
    "        if value_column[i] == True:\n",
    "            NULL_value_position.append((i, j))\n",
    "print(NULL_value_position)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 计算n阶差商\n",
    "\n",
    "计算$n$阶差商 $f{[{x_0},{x_1},{x_2},{\\cdots},{x_n}]}$.\n",
    "$x_i$   所有插值节点的横坐标集合\n",
    "$f_i$   所有插值节点的纵坐标集合\n",
    "返回$x_i$的i阶差商($i$为$x_i$长度减1)\n",
    "> a. 必须确保$x_i$与$f_i$长度相等\n",
    ">\n",
    "> b. 由于用到了递归，所以留意不要爆栈了\n",
    ">\n",
    "> c. 递归减递归(每层递归包含两个递归函数), 每层递归次数呈二次幂增长，总次数是一个满二叉树的所有节点数量(所以极易栈溢出)\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [],
   "source": [
    "def get_order_diff_quot(xi = [], fi = []):\n",
    "    if len(xi) > 2 and len(fi) > 2:\n",
    "         return (get_order_diff_quot(xi[:len(xi) - 1], fi[:len(fi) - 1]) - get_order_diff_quot(xi[1: len(xi)], fi[1: len(fi)])) / float(xi[0] - xi[-1])\n",
    "    return (fi[0] - fi[1]) / float(xi[0] - xi[1])\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 获得$W_i{(x)}$函数\n",
    "\n",
    "$W_i$的含义举例: ${W_1} = {(x - {x_0})}$;   ${W_2} = {(x - {x_0})(x - {x_1})}$;  ${W_3} = {(x - {x_0})(x - {x_1})(x - {x_2})}$\n",
    "\n",
    "$ i: $  i阶(i次多项式).\n",
    "\n",
    "$ x_i: $  所有插值节点的横坐标集合.返回$ W_i{(x)} $函数\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [],
   "source": [
    "def get_Wi(i=0, xi=[]):\n",
    "    def Wi(x):\n",
    "        result = 1.0\n",
    "        for each in range(i):\n",
    "            result *= (x - xi[each])\n",
    "        return result\n",
    "    return Wi\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 获得牛顿插值函数\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [],
   "source": [
    "def get_Newton_inter(xi=[], fi=[]):\n",
    "    def Newton_inter(x):\n",
    "        result = fi[0]\n",
    "        for i in range(2, len(xi)):\n",
    "            result += (get_order_diff_quot(xi[:i], fi[:i]) * get_Wi(i - 1, xi)(x))\n",
    "        return result\n",
    "\n",
    "    return Newton_inter\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [],
   "source": [
    "# 自定义列向量插值函数。s为列向量\n",
    "def Newton_ployinterp_column(s):\n",
    "    # 剔除空值\n",
    "    y = s[s.notnull()]\n",
    "    Nx = get_Newton_inter(y.index, list(y))\n",
    "    return Nx\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [],
   "source": [
    "# 逐个元素判断是否需要插值\n",
    "for i in data.columns:\n",
    "    Newton = Newton_ployinterp_column((data[i]))\n",
    "    for j in range(len(data)):\n",
    "        if (data[i].isnull())[j]:\n",
    "            data[i][j] = Newton(j)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "             A             B           C\n",
      "0   235.833300  3.240343e+02  478.323100\n",
      "1   236.270800  3.256379e+02  515.456400\n",
      "2   238.052100  3.280897e+02  517.090900\n",
      "3   235.906300  9.697839e+02  514.890000\n",
      "4   236.760400  2.688324e+02  494.228728\n",
      "5   227.977182  4.040480e+02  486.091200\n",
      "6   237.416700  3.912652e+02  516.233000\n",
      "7   238.656300  3.808241e+02  486.684788\n",
      "8   237.604200  3.880230e+02  435.350800\n",
      "9   238.031300  2.064349e+02  487.675000\n",
      "10  235.072900  1.948308e+02  611.336742\n",
      "11  235.531300  4.000787e+02  660.234700\n",
      "12  237.580239  4.112069e+02  621.234600\n",
      "13  234.468800  3.952343e+02  611.340800\n",
      "14  235.500000  3.448221e+02  643.086300\n",
      "15  235.635400  3.856432e+02  642.348200\n",
      "16  234.552100  4.016234e+02  655.493609\n",
      "17  236.000000  4.096489e+02  602.934700\n",
      "18  235.239600  4.168795e+02  589.345700\n",
      "19  235.489600  6.553214e+06  556.345200\n",
      "20  236.968800  5.015058e+07  538.347000\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "d:\\electric-leak-recognition\\venv\\lib\\site-packages\\ipykernel_launcher.py:3: FutureWarning: As the xlwt package is no longer maintained, the xlwt engine will be removed in a future version of pandas. This is the only engine in pandas that supports writing in the xls format. Install openpyxl and write to an xlsx file instead. You can set the option io.excel.xls.writer to 'xlwt' to silence this warning. While this option is deprecated and will also raise a warning, it can be globally set and the warning suppressed.\n",
      "  This is separate from the ipykernel package so we can avoid doing imports until\n"
     ]
    }
   ],
   "source": [
    "# 输出结果\n",
    "print(data)\n",
    "data.to_excel(outputfile, header=None, index=False)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}